This application is also related to co-pending U.S. Patent Applications entitled xe2x80x9cMETHOD AND SYSTEM OF CONTROLLING TRANSFER OF DATA BY UPDATING DESCRIPTORS IN DESCRIPTOR RINGSxe2x80x9d; xe2x80x9cMETHOD AND SYSTEM OF ROUTING NETWORK BASED DATA USING FRAME ADDRESS NOTIFICATIONxe2x80x9d; and xe2x80x9cMETHOD AND APPARATUS FOR CONTROLLING NETWORK DATA CONGESTIONxe2x80x9d all filed Sep. 30, 1998, in the name of the same inventor as this application and assigned to the same assignee. Accordingly, the contents of all the related applications are incorporated by reference into this application.
1. Field of the Invention
This invention relates generally to a method and system for controlling the transfer of network based data arranged in frames between a host and controller having shared memory and, more particularly, to a fencepost caching mechanism for receiving and transmitting descriptor ring updates.
2. Background of the Prior Art
Data networks have become increasingly important in day-to-day activities and business applications. Most of these networks are a packet-switched network, such as the Internet, which uses a transmission control protocol, frequently referred to as TCP/IP. The Transmission Control Protocol (TCP) manages the reliable reception and transmission of network traffic, while the Internet Protocol (IP) is responsible for routing and ensuring that the packets are sent to a correct destination.
In a typical network, a mesh of transmission links are provided, as well as switching nodes and end nodes. End nodes typically ensure that any packet is received and transmitted on the correct outgoing link to reach its destination. The switching nodes are typically referred to as packet switches, or routers, or intermediate systems. The sources and destinations in data traffic (the end nodes) can be referred to as hosts and end systems. These host and end systems typically consist of personal computers, workstations, and other terminals.
The network infrastructure employs routers that can determine optimum paths by using routing algorithms. The routers also switch packets arriving at an input port to an output port based on the routing path for each packet. The routing algorithms (or routing protocol) are used to initialize and maintain routing tables that consist of entries that point to a next router to send a packet with a given destination address. Typically, fixed costs are assigned to each link in the network and the cost reflects link bandwidth and/or cost. The least cost paths can be determined by a router after it exchanges network topology and link cost information with other routers. A traditional router is basically a computer dedicated to the task of moving packets of data from one channel to the next. Like most computers, it consists of a central MPU, bus, and memory but distinguished by its possession of multiple I/O channels usually managed by dedicated communication controllers.
A communication controller relieves a central MPU of many of the tasks associated with transmitting and receiving frames. A frame (sometimes referred to as a packet) is a single communication element which can be used for both link-control and data transfer purposes.
Most controllers include a direct memory access (DMA) device or function which provides access to an external shared memory resource. The controller allows either DMA or non-DMA data transfers. The controller accepts a command from the MPU, executes the command, and provides an interrupt and result back to the MPU.
These command operations often entail movement or control of various data structures. Data structures are used for the temporary storage of frames. They play a key role in the architecture of any successful router. Implementations vary, but generally one finds two species: ring buffers and linked lists.
A ring buffer consists of two components: descriptors and frame data buffers. Descriptors both describe and point to a respective frame data buffer within a shared system memory between the host and a controller. The descriptor ring is a circular queue composed of multiple descriptor entries containing pointers and information describing data buffers. Each descriptor ring is dedicated to a specific memory and mapped to specific channels within the controller. Each two-word descriptor entry within a descriptor ring is associated with one specific buffer in a system memory, such as the shared system memory between a network device, such as a controller and host.
The frame buffers are typically defined as blocks of memory containing frames for transmission or providing space for frame reception. Each transmit channel and each receive channel would use a dedicated descriptor ring. Whenever a frame exceeds the finite capacity of a single frame data buffer, the frame is said to xe2x80x9cspanxe2x80x9d the buffer. An ownership bit in the first word of each descriptor indicates whether the host or controller owns the associated frame data buffer.
Ownership follows a specific protocol that must be adhered to by the controller and the host. Once ownership of a descriptor has been relinquished to the other device or host, no part of the descriptor or its associated buffer may be altered. The host gives the network device ownership of empty frame data buffers for frame transmission. Conversely, the network device passes ownership back to the host for transmit frame data buffers it has used and receive frame data buffers it has filled.
For frame reception, the host is required to provide the controller or other network device with ownership of contiguous descriptors pointing to empty frame data buffers. Once a frame is fully received by the controller, ownership of its constituent descriptors is then reassigned. The host is signaled regarding the event via an interrupt. The host is typically obligated to read a Master Interrupt Register (MIR) in order to surmise the meaning of the signal. Once this is accomplished, the frame may then be dispatched in some fashion and ownership of the relevant descriptors return to the controller.
In typical operation, the host xe2x80x9cfollowsxe2x80x9d the controller or other network device around the ring leaving xe2x80x9cemptyxe2x80x9d descriptors in its wake for the controller to use. If the device gets too far ahead of the host, it can wrap around the descriptor ring and encounter descriptors it does not own. As a result, incoming frames could be lost if this were to occur.
For frame transmission, the device xe2x80x9cfollowsxe2x80x9d the host round a transmit descriptor ring leaving used descriptors in its wake for the host to reclaim. The host transfers ownership of descriptors to the device when it has one or more frames ready for transmission. Once a frame is fully transmitted by the device, ownership of its constituent descriptors is transferred back to the host for reuse. The host is signaled regarding this event via an interrupt.
In certain applications, the host may elect to use data buffers which are smaller in size than the frames that are actually received or transmitted. A single frame may therefore be forced to span multiple buffers. This type of system would allow frames to be dissected (scattered on reception) or assembled (gathered on transmission) by the controller. Multiple buffers can hold the constituent pieces of a frame by xe2x80x9cchainingxe2x80x9d or grouping the associated descriptors together. The chained descriptors are consecutive entries in a descriptor ring with the end-of-frame flag set in the terminating descriptor of the chain. In other words, data buffer of a descriptor entry which is owned but whose end-of-frame flag (EOF) is not set is considered to be part of a frame and not an entire frame. Scatter/gather buffering benefits frames crossing multiple layers of communication protocol. Rather than laboriously copying large buffers from one service layer to the next, small pointers are passed instead. These pointers are ultimately converted into or generated from frame descriptors.
During reception of large frames, the device xe2x80x9cchainsxe2x80x9d or groups the descriptors together one by one as it fills each successive frame data buffer. When the end of the frame is received and transferred to the shared system memory, the end-of-frame flag is set in the terminating descriptor of the chain. During transmission, the controller is able to construct sequentially a single frame from contents of chained buffers. Transmission of the frame terminates only when it encounters a buffer whose descriptor has set the end-of-frame flag.
Fencepost buffering gets its name from the idea that rather than successively updating each spanned descriptor, only the terminal descriptors need to be altered. Thus, at most one, in the case that a packet spans a single descriptor, or at most two descriptors ever need to be updated. This relaxes the dependency between packet size and buffer management overhead. While the reduction of descriptor activity in turn reduces total bus traffic and further reduces packet latency, latency issues persist.
Therefore, a need existed to provide a system and method which reduces frame transfer latency in fencepost procedures. The system and method must permit descriptor transfer to and from memory in a reliable and efficient manner. The system and method must further reduce complications arising from instrumenting a ringbuffer. The system and method must further avoid resource race conditions between DMA and the CPU.
Accordingly, it is an object of this invention to provide a caching mechanism and method to support fencepost procedures.
It is a further object of this invention to provide a system and method which reduces frame transfer latency in fencepost procedures.
It is another object of this invention to provide a system and method which permit descriptor transfer to and from memory in a reliable and efficient manner.
It is still another object of this invention to provide a system and method which reduce complications arising from instrumenting a ringbuffer.
It is another object of this invention to provide a system and method which avoid resource race conditions between DMA and the CPU.
In accordance with one embodiment of this invention, a method for reducing transfer latencies in fencepost buffering is disclosed. In the method a cache is provided between a network controller and a host entity with shared memory. The cache is divided into a dual cache having a top cache and a bottom cache. A first and second descriptor address location are fetched from shared memory. The two descriptors are discriminated from one another in that the first descriptor address location is a location of an active descriptor and the second descriptor address location is a location of a reserve descriptor. The active descriptor is copied to the top cache. A command is issued to DMA for transfer of the active descriptor. The second descriptor address location is then copied into the first descriptor address. The next descriptor address location from external memory is then fetched and placed in the second descriptor address location.
In accordance with another embodiment of this invention, a method for reducing transfer latencies in fencepost buffering having chained descriptors is disclosed. The method provides a cache between a network controller and a network controller having shared memory wherein the cache has a top cache and a bottom cache. A first and second descriptor address location is fetched from shared memory. The first descriptor address location is a location of an active descriptor and the second descriptor address location is a location of a look-ahead descriptor. The ownership of the terminal descriptors describing a frame need to be updated. This requires writing a modified End of Frame (EOF) descriptor to cache before writing the Start of Package (SOP) descriptor. Commands are then issued to DMA for transfer of both cached descriptors to external shared memory. The second descriptor address location is then copied into the first descriptor address. The next descriptor address location from external memory is then fetched and placed in the second descriptor address location.
The foregoing and other objects, features and advantages of this invention will be apparent from the following more particular description of the preferred embodiments of the invention as illustrated in the accompanying drawings.